package org.example.everyday;

import java.util.Timer;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/3/17 10:41
 */
public class Lc720 {

    public static void main(String[] args) {
        Lc720 lc720 = new Lc720();
        String[] words = {"w","t","wo","wor","worl", "world"};
        String result = lc720.longestWord(words);
        System.out.println(result);
    }

    public String longestWord(String[] words){
        Trie trie = new Trie();
        for(String word : words){
            trie.insert(word);
        }
        String longest = "";
        for(String word :words){
            if(trie.search(word)){
                if(word.length() > longest.length() || (word.length() == longest.length()
                        && word.compareTo(longest) < 0)){
                    longest =  word;
                }
            }
        }
        return longest;
    }



    class Trie{
        Trie[] children;
        boolean isEnd;

        public Trie(){
            children = new Trie[26];
            isEnd = false;
        }
        public  void insert(String word){
            Trie node = this;
            for(int i = 0; i < word.length(); i++){
                char ch = word.charAt(i);
                int index = ch - 'a';
                if(node.children[index] == null){
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }

        public boolean search(String word){
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                int index = ch - 'a';
                if(node.children[index] == null || !node.children[index].isEnd){
                    return false;
                }
                node = node.children[index];
            }
            return node != null && node.isEnd;
        }
    }
}
